Field of the Invention
The present invention relates to the collection of data from range-finding laser devices (RFLDs), such as those used for Light Detection and Ranging (LIDAR) applications, to generate point clouds capable of creating maps of and/or within structures. The present invention additionally relates to accurately tracking the position of a RFLD using a Simultaneous Localization and Mapping (SLAM) process. The invention relates to apparatus, systems, and methods for collecting and processing RFLD data to generate a map image and to apparatus, systems, and methods for tracking the position of a RFLD device.
Description of Related Art
Light Detection and Ranging (LIDAR) is often used to measure the distances of objects from a LIDAR range-finding laser device (RFLD). In such applications, the RFLD emits laser pulses, and a detector positioned on or near the RFLD detects reflections of the laser pulses from objects around the RFLD. The travel time from the time when each pulse is emitted to the time when the reflection from that pulse is detected is used to calculate the distance of the point on the object from which the laser pulse is reflected.
When used for mapping an area surrounding the RFLD, a LIDAR system typically uses data from a Global Positioning System (GPS) to track the precise location of the LIDAR system. The precise location of the RFLD is necessary, for example, if data from the RFLD is moved and used to create an image or digital map of the surroundings of the RFLD over time as the RFLD is moved. A difficulty arises, however, when LIDAR is to be used in this way where GPS signals are not available. Locations where GPS signals are normally not available include the interiors of buildings, caves, and wherever physical objects or electromagnetic fields block or interfere with GPS signals.
One type of solution to the problem LIDAR mapping without GPS involves the pavement of transmitters, receivers, reflectors, or other location markers at known locations in the environment or structure being mapped. This allows communicating with receivers, transmitters, or sensors on a range-finding device that allow the position of the LIDAR system to be triangulated or otherwise calculated. This type of solution is not satisfactory for many applications, however, because the positioning of markers at precisely known locations is time consuming and, for large or complex structures, may require very large numbers of transmitters.
US 2007/0185681 A1 describes a system and method for mapping a room without GPS. The system includes a rangefinder, an inertial sensor on the rangefinder, and a processor coupled the rangefinder and the inertial sensor. The processor produces a virtual room reconstruction based on a set of range measurements from the rangefinder and inertial measurements from an inertial sensor. The system is used to map a building by repeating a two-step process in which a range-finder measures the distance to one or more walls while information about the attitude and position of the range-finder is obtained from a six-axis inertial sensor attached to the range-finder. The accuracy of this system and method is limited, however, in part because errors in determining the position of the range-finder accumulate quickly over time. This, in turn, limits the accuracy of a map resulting from the incorporation of inaccurate position data by the processor.
U.S. Pat. No. 7,991,576 B2 describes an indoor navigation system and method that includes generating an attitude estimate of a cane, determining the heading direction, and determining a position of the person holding the cane. The attitude (pitch, roll, yaw) of the cane is estimated using a 3-axis gyroscope and laser-scan measurements of structural planes in the building. Heading is extracted from a yaw component of the cane's attitude estimate and provides a heading measurement to a position filter. The position of the person is estimated using heading estimates, linear velocity measurements from a pedometer, and relative coordinates of known corner features detected by the laser scanner. A laser scanner is used to detect corners for which the locations have been determined in advance. One significant limitation of this system and method is that the corner features required for the method must be known a priori from building blueprints or from another source, which limits their use to locations for which maps, blueprints, or other detailed position data is available. Additionally, the transfer of coordinates for known features into the system is required for each location in which the cane is to be used.
US 2013/0120736 A1 describes a method and a three-dimensional (3D) scanning device with a reactive linkage mechanism that are used to collected data that can be used for generating a point cloud. The process involves a data association hat identifies a common feature detected by a laser scanner at two different positions, or poses, that identify two surfaces of the common feature. A system of constraints is formed that links feature matches to corrections applied to the pose of the laser scanner. A registration algorithm is used to project range measurements into a non-registered 3D point cloud. A function specifying a six degree of freedom pose of the laser scanner with respect to a ground coordinate frame is used to determine a trajectory of the scanner. A workspace of the environment is discretized into a 3D grid of volume elements and statistics are computed for each voxel based on the set of scan points that fall within its boundaries. To account for non-uniform sampling of the environment and boundary effects, 3D grids are computed at multiple resolutions and offsets. An iterative optimization algorithm is then used to estimate the scanner trajectory and register the point cloud to produce an accurate 3D map. This process requires significant computing power and does not provide the speed or accuracy of systems using markers of known reference locations.
Simultaneous Localization and Mapping (SLAM) involves building, extending and improving a map of the surroundings of a moving robot and simultaneously determining the location of the robot with respect to the map. As a robot moves through a structure for which the robot has no defined map or known landmarks, a SLAM process can be used to calculate the estimated pose of the robot from measured headings and odometer readings. SLAM systems typically include inertial measurement units (IMUS) or other sensors to track position and orientation, or pose. Unfortunately, the accuracy of the pose calculated in this way is limited because of an accumulation of relatively small errors over time that result in large errors in the calculated pose.
Existing technologies and services for capturing data and rendering a layout of a building interior are relatively expensive or slow or both. Technologies that provide very accurate results are expensive and slow. Many are too bulky or fragile to be portable and the techniques have not been developed that support localizing, or determining the position of the equipment as it moves. Scanning large volume areas such as millions of square feet in 6-10 hours at a reasonable cost is currently not possible. Existing systems provides high resolution scanning technology that is either placed in a sequence of fixed locations or slowly moved on a cart at a constant speed. In both cases, the scanning process is time consuming and a fixed or limited height of scanning limits coverage. In the case of a moving cart, obstacles such as office cubicles have to be navigated to expose all interior spaces to the laser scan, which also slows the process.
Thus, a need remains in the art for a mapping system and method capable of accurately mapping structures, preferably in real time, without the use of GPS or the need for marking known locations with positional markers.